﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCodeSolutions
{
    class LeetCode70 : LeetCodeBase
    {
        public override void Execute()
        {
            int n = 2;
            CommonFuntions.Print(ClimbStairs(n));
        }

        public int ClimbStairs(int n)
        {
            Dictionary<int, int> cache = new Dictionary<int, int>();
            return Calcu(n, cache);
        }

        public int Calcu(int n, Dictionary<int, int> cache)
        {
            if (n == 1 || n == 2) return n;
            if (cache.ContainsKey(n)) return cache[n];
            cache[n - 1] = Calcu(n - 1, cache);
            cache[n - 2] = Calcu(n - 2, cache);

            return cache[n - 1] + cache[n - 2];
        }
    }
}
